﻿using System;
using System.Collections.Generic;
using System.Linq;
/// <summary>
/// 统计矩形数量的众数（出现频率最高的数量）
/// 归一化矩形坐标（转换为中心点并除以图片尺寸）
/// K-Means聚类（多次迭代优化）
/// 取每个聚类的中位数矩形（抗噪性好）
/// 反归一化并转换回左上角坐标
/// 按位置排序（从上到下，从左到右）
/// </summary>
public struct DetectedRect
{
    public float X;
    public float Y;
    public float Width;
    public float Height;

    public DetectedRect(float x, float y, float width, float height)
    {
        X = x;
        Y = y;
        Width = width;
        Height = height;
    }

    public float CenterX => X + Width / 2f;
    public float CenterY => Y + Height / 2f;
    public float Area => Width * Height;
}

public class RobustRectMerger
{
    private readonly float _imgWidth;
    private readonly float _imgHeight;
    private readonly float _positionTolerance;
    private readonly float _sizeTolerance;
    private readonly float _aspectTolerance;
    private readonly int _minOccurrences;

    public RobustRectMerger(float imgWidth, float imgHeight,
                          float positionTolerance = 0.15f,
                          float sizeTolerance = 0.4f,
                          float aspectTolerance = 0.3f,
                          int minOccurrences = 5)
    {
        _imgWidth = imgWidth;
        _imgHeight = imgHeight;
        _positionTolerance = Math.Clamp(positionTolerance, 0.05f, 0.3f);
        _sizeTolerance = Math.Clamp(sizeTolerance, 0.2f, 0.8f);
        _aspectTolerance = Math.Clamp(aspectTolerance, 0.1f, 0.5f);
        _minOccurrences = Math.Max(minOccurrences, 1);
    }

    public List<DetectedRect> MergeRects(List<List<DetectedRect>> rectLists)
    {
        // 0. 处理空输入
        if (rectLists == null || rectLists.Count == 0 || rectLists.All(list => list.Count == 0))
            return new List<DetectedRect>();

        // 1. 展平所有矩形到单个列表，并添加来源信息
        var allRects = new List<(DetectedRect rect, int sourceIndex)>();
        for (int i = 0; i < rectLists.Count; i++)
        {
            foreach (var rect in rectLists[i])
            {
                allRects.Add((rect, i));
            }
        }

        if (allRects.Count == 0) return new List<DetectedRect>();

        // 2. 基于位置和尺寸的分组（尺寸无关）
        var groups = CreateSizeAgnosticGroups(allRects);

        // 3. 为每个组创建合并后的矩形
        var mergedRects = MergeGroups(groups);

        // 4. 按位置排序（从上到下，从左到右）
        mergedRects = mergedRects
            .OrderBy(r => r.Y)
            .ThenBy(r => r.X)
            .ToList();

        return mergedRects;
    }

    private List<List<(DetectedRect rect, int sourceIndex)>> CreateSizeAgnosticGroups(
        List<(DetectedRect rect, int sourceIndex)> allRects)
    {
        // 首先按位置分组（忽略尺寸）
        var positionGroups = new List<List<(DetectedRect rect, int sourceIndex)>>();
        var positionVisited = new bool[allRects.Count];

        for (int i = 0; i < allRects.Count; i++)
        {
            if (positionVisited[i]) continue;

            var group = new List<(DetectedRect rect, int sourceIndex)> { allRects[i] };
            positionVisited[i] = true;

            for (int j = i + 1; j < allRects.Count; j++)
            {
                if (positionVisited[j]) continue;

                if (IsPositionSimilar(allRects[i].rect, allRects[j].rect))
                {
                    group.Add(allRects[j]);
                    positionVisited[j] = true;
                }
            }

            positionGroups.Add(group);
        }

        // 然后按尺寸细分（仅在位置组内进行）
        var finalGroups = new List<List<(DetectedRect rect, int sourceIndex)>>();

        foreach (var posGroup in positionGroups)
        {
            // 如果位置组内所有矩形来自同一图片，直接作为一组
            if (posGroup.All(r => r.sourceIndex == posGroup[0].sourceIndex))
            {
                finalGroups.Add(posGroup);
                continue;
            }

            // 按尺寸细分
            var sizeGroups = new List<List<(DetectedRect rect, int sourceIndex)>>();
            var sizeVisited = new bool[posGroup.Count];

            for (int i = 0; i < posGroup.Count; i++)
            {
                if (sizeVisited[i]) continue;

                var sizeGroup = new List<(DetectedRect rect, int sourceIndex)> { posGroup[i] };
                sizeVisited[i] = true;

                for (int j = i + 1; j < posGroup.Count; j++)
                {
                    if (sizeVisited[j]) continue;

                    if (IsSizeSimilar(posGroup[i].rect, posGroup[j].rect))
                    {
                        sizeGroup.Add(posGroup[j]);
                        sizeVisited[j] = true;
                    }
                }

                sizeGroups.Add(sizeGroup);
            }

            finalGroups.AddRange(sizeGroups);
        }

        return finalGroups;
    }

    private bool IsPositionSimilar(DetectedRect a, DetectedRect b)
    {
        // 计算位置距离（中心点距离）
        float centerDist = Distance(a.CenterX, a.CenterY, b.CenterX, b.CenterY);

        // 使用相对容差：基于矩形平均尺寸
        float avgSize = (a.Width + a.Height + b.Width + b.Height) / 4f;
        float maxDist = avgSize * _positionTolerance;

        return centerDist <= maxDist;
    }

    private bool IsSizeSimilar(DetectedRect a, DetectedRect b)
    {
        // 尺寸相似性（相对百分比）
        float widthRatio = Math.Abs(a.Width - b.Width) / Math.Max(a.Width, b.Width);
        float heightRatio = Math.Abs(a.Height - b.Height) / Math.Max(a.Height, b.Height);

        // 宽高比相似性
        float aspectA = a.Width / Math.Max(1, a.Height);
        float aspectB = b.Width / Math.Max(1, b.Height);
        float aspectRatio = Math.Abs(aspectA - aspectB) / Math.Max(aspectA, aspectB);

        return widthRatio <= _sizeTolerance &&
               heightRatio <= _sizeTolerance &&
               aspectRatio <= _aspectTolerance;
    }

    private float Distance(float x1, float y1, float x2, float y2)
    {
        float dx = x2 - x1;
        float dy = y2 - y1;
        return (float)Math.Sqrt(dx * dx + dy * dy);
    }

    private List<DetectedRect> MergeGroups(List<List<(DetectedRect rect, int sourceIndex)>> groups)
    {
        var mergedRects = new List<DetectedRect>();

        foreach (var group in groups)
        {
            // 过滤掉出现次数不足的组
            var uniqueSources = group.Select(r => r.sourceIndex).Distinct().Count();
            if (uniqueSources < _minOccurrences) continue;

            // 计算稳健的中心位置（中位数）
            float medianX = group.Select(r => r.rect.CenterX).Median();
            float medianY = group.Select(r => r.rect.CenterY).Median();

            // 计算稳健的尺寸（加权中位数）
            float medianWidth = group.Select(r => r.rect.Width).Median();
            float medianHeight = group.Select(r => r.rect.Height).Median();

            // 从中心点转换回左上角坐标
            float x = medianX - medianWidth / 2f;
            float y = medianY - medianHeight / 2f;

            mergedRects.Add(new DetectedRect(x, y, medianWidth, medianHeight));
        }

        return mergedRects;
    }

    // 移除重叠矩形（使用非极大值抑制）
    private List<DetectedRect> RemoveOverlappingRects(List<DetectedRect> rects, float overlapThreshold)
    {
        if (rects.Count <= 1) return rects;

        var result = new List<DetectedRect>();
        var rectScores = rects.Select(r => r.Area).ToList();

        while (rects.Count > 0)
        {
            // 找到最大面积的矩形
            int maxIndex = 0;
            float maxScore = rectScores[0];
            for (int i = 1; i < rects.Count; i++)
            {
                if (rectScores[i] > maxScore)
                {
                    maxScore = rectScores[i];
                    maxIndex = i;
                }
            }

            var maxRect = rects[maxIndex];
            result.Add(maxRect);

            // 移除与最大矩形重叠的矩形
            var newRects = new List<DetectedRect>();
            var newScores = new List<float>();

            for (int i = 0; i < rects.Count; i++)
            {
                if (i == maxIndex) continue;

                float iou = CalculateIOU(maxRect, rects[i]);
                if (iou < overlapThreshold)
                {
                    newRects.Add(rects[i]);
                    newScores.Add(rectScores[i]);
                }
            }

            rects = newRects;
            rectScores = newScores;
        }

        return result;
    }

    // 计算IOU
    private float CalculateIOU(DetectedRect rect1, DetectedRect rect2)
    {
        float x1 = Math.Max(rect1.X, rect2.X);
        float y1 = Math.Max(rect1.Y, rect2.Y);
        float x2 = Math.Min(rect1.X + rect1.Width, rect2.X + rect2.Width);
        float y2 = Math.Min(rect1.Y + rect1.Height, rect2.Y + rect2.Height);

        float interWidth = Math.Max(0, x2 - x1);
        float interHeight = Math.Max(0, y2 - y1);
        float interArea = interWidth * interHeight;

        float area1 = rect1.Width * rect1.Height;
        float area2 = rect2.Width * rect2.Height;

        float unionArea = area1 + area2 - interArea;

        if (unionArea <= 0) return 0;

        return interArea / unionArea;
    }
}

// 扩展方法用于计算中位数
public static class EnumerableExtensions
{
    public static float Median(this IEnumerable<float> source)
    {
        var sorted = source.OrderBy(n => n).ToArray();
        int count = sorted.Length;

        if (count == 0) return 0;
        if (count % 2 == 0)
        {
            return (sorted[count / 2 - 1] + sorted[count / 2]) / 2f;
        }
        return sorted[count / 2];
    }
}